package com.zhuang.linkedlist.linked;

import com.zhuang.linkedlist.abstractclass.AbstractList;

public class SingleLinkedList<E> extends AbstractList<E> {
	// 约定：在说链表查找元素位置时，我还是将index称之为索引
	private Node first;

	private static class Node<E> {
		Node<E> next;
		E element;

		public Node(Node next, E element) {
			this.next = next;
			this.element = element;
		}

	}

	// 遍历获取节点
	private Node<E> node(int index) {
		Node node = first;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}

	@Override
	public E get(int index) {
		checkElementIndex(index);
		return node(index).element;
	}

	@Override
	public E set(int index, E element) {
		// 你在指定索引上去修改元素值是 element ，原来返回原来的值
		checkElementIndex(index);
		// 1.获得index上的node
		Node<E> node = node(index);
		// 2.拿到原来的老值
		E oldElement = node.element;
		// 3.去进行修改
		node.element = element;
		// 4.return 原来的老值
		return oldElement;
	}

	@Override
	public void add(int index, E element) {
		checkPostionIndex(index);
		if (index == 0) {
			// 为链表头
			first = new Node(first, element);
		} else {
			// 获得 index -1 的Node同还要获得index节点去改变index-1上的next ，同时去将next节点的内存值赋值给新new出来的Node
			// 获得前面的节点
			Node<E> pre = node(index - 1);
			// 前面的节点赋值给新的next节点
			Node<E> next = pre.next;
			pre.next = new Node<E>(next, element);
		}
		size++;
	}

	@Override
	public E remove(int index) {
		checkElementIndex(index);
		Node<E> oldNode = first;
		if (index == 0) {
			first = first.next;
		} else {
			// 拿到前面的节点
			Node<E> pre = node(index - 1);
			// 前面节点的后面是要被删除的节点
			oldNode = pre.next;
			// 删除节点的后面赋值给前面节点 删除节点
			pre.next = oldNode.next;
		}
		size--;
		return oldNode.element;
	}

	@SuppressWarnings("unchecked")
	@Override
	public int indexOf(E element) {
		// 查找有没有element元素，如果有返回element元素的索引，如果没有则返回-1
		Node<E> node = first;
		int index = 0;
		if (element == null) {
			for (Node<E> i = node; node != null; node = node.next) {
				if (element == node.element) {
					return index;
				}
				index++;
			}
		} else {
			for (Node<E> i = node; node != null; node = node.next) {
				if (element == node.element) {
					return index;
				}
				index++;
			}
		}
		return -1;
	}

	@Override
	public void clear() {
		size = 0;
		first = null;
	}

	// 判断索引是否合法
	private boolean isElementIndex(int index) {
		// 满足条件
		return index >= 0 && index < size;
	}

	// 检查元素索引
	private void checkElementIndex(int index) {

		if (!isElementIndex(index)) {
			throw new IndexOutOfBoundsException(": Index: " + index + ", Size: " + size);
		}

	}

	// 检查索引位置
	private void checkPostionIndex(int index) {
		if (!isPostionIndex(index)) {
			throw new IndexOutOfBoundsException(": Index: " + index + ", Size: " + size);
		}
	}

	// 检查索引的合法性
	private boolean isPostionIndex(int index) {
		return index >= 0 && index <= size;
	}

	@Override
	public String toString() {
		if (size == 0) {
			return "[]";
		}
		StringBuilder sb = new StringBuilder().append("[");
		Node node = first;
		for (Node i = node; i != null; i = i.next) {
			sb.append(i.element);
			if (i.next == null) {
				return sb.append("]").toString();
			}
			sb.append(",");
		}
		return sb.toString();
	}
}
